//https://www.nowcoder.com/practice/00de97733b8e4f97a3fb5c680ee10720?tpId=13&tqId=23448&ru=%2Fpractice%2F4436c93e568c48f6b28ff436173b997f&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思想：官方实现:map实现;
//思想：自己实现:list+map;

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <climits>
#include <unordered_map>

using namespace std;

#include <iterator>

class Solution
{
public:
    unordered_map<char, int> mp;
    //记录输入的字符串
    string s;
    //Insert one char from stringstream
    void Insert(char ch) {
        //插入字符
        s += ch; 
        //哈希表记录字符出现次数
        mp[ch]++;
    }
    //return the first appearence once char in current stringstream
    char FirstAppearingOnce() {
        //遍历字符串
        for(int i = 0; i < s.length(); i++)
            //找到第一个出现次数为1的
            if(mp[s[i]] == 1)
                return s[i];
        //没有找到
        return '#';
    }
};

class Solution2
{
public:
   std::list<char> c_list;
   std::map<char,std::list<char>::iterator> c_map;
  //Insert one char from stringstream
    void Insert(char ch) {
        if (c_map.find(ch)!=c_map.end()) {
            if (c_map[ch]!=c_list.end()) {
                c_list.erase(c_map[ch]);
                c_map[ch]=c_list.end();
            }
        }else {
           c_list.emplace_back(ch);
           auto last= c_list.end();
           std::advance(last, -1);
           c_map[ch]=last;
        }
    }
    char FirstAppearingOnce() {
        char res_char='#';
        if (!c_list.empty()) res_char=*c_list.begin();
        return res_char;
    }

};
